\documentclass[a4paper,10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}


%opening
\title{Topological HMMs}
\author{}

\begin{document}

\maketitle

\section{HMM}

Let $G$ be the given unknown graph. Assume that the topology of the graph can be described by a specific configuration of frequently occuring subgraphs.
That is, $G=\bigcup_{i=1}^{k}F_{i} $ for some set of frequent subgraphs $\{F_1, ..., F_k\}$. We will denote by clusters, the frequent subgraphs from the training set.

Let $q_i$ be a hidden state of the model. $q_i$ is this hidden "true" assignment of subgraphs to frequent subgraphs of the partially observed graph.
The state transition probability  $\mathcal{A}=\{a_{ij}\}$ is $a_{ij}=P(q_{t+1}=e_j|q_t=e_i)$ and determines the probability going from a specific
one graph of clusters to another graph of clusters.

We have the condition that $\sum_{j=1}^{N} a_{ij}=1$.

Let $R$ be the number of distinct observation per hidden state. Let $N$ be the number of hidden states.
We also have the emission probability distribution, $\mathcal{B}=\{ b_j(k) \}$ where $b_j(k)=P(o_k \text{ at time t }|q_t=e_j), 1\leq k \leq R, 1 \leq j \leq N$.


For a specific observed partial graph, we will chose to limit the number of possible hidden states. We will only consider those frequent subgraphs $F_i$
that have atleast one vertex in common with the partial graph. We will also force that the partial observed graph must be a subgraph of union of the graphs in a hidden state.

There are three basic problems assigned to an HMM, namely evaluation, decoding and learning.


Given a observation sequence $O=o_1, ..., o_T$ and a model $\lambda=[\mathcal{A}, \mathcal{B}]$, what is the probability of
this model given the observation sequence?
In a sense, we are then asking ourselves, what is the probability of this hypothesis?

So how would we define $\mathcal{A}$ and $\mathcal{B}$?
For each hypothesis, that is an assignment of clusters to the subgraphs of the partial graph, we would form $\mathcal{A}$ and $\mathcal{B}$.
$\mathcal{A}$ is the probability matrix of going from one hidden state to another.
Since a hidden state is a assignment of the subgraphs to clusters, 


%We have the initial state distribution $\pi=\{ \pi_0 \}$, where $\pi_i=P(q_0=e_i)$



\end{document}
